package com.leetcode.sorts.string;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @Author: WuPeng
 * @Date: 2021/5/31 11:00 上午
 *
 * 151: 翻转字符串里的单词
 * 给你一个字符串 s ，逐个翻转字符串中的所有单词 。
 * 单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
 * 请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
 *
 * 说明：
 *      输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
 *      翻转后单词间应当仅用一个空格分隔。
 *      翻转后的字符串中不应包含额外的空格。
 * 
 * 示例 1：
 *      输入：s = "the sky is blue"
 *      输出："blue is sky the"
 *
 * 示例 2：
 *      输入：s = " hello world "
 *      输出："world hello"
 *      解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
 *
 * 示例 3：
 *      输入：s = "a good  example"
 *      输出："example good a"
 *      解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。
 *
 * 示例 4：
 *      输入：s = "  Bob    Loves  Alice   "
 *      输出："Alice Loves Bob"
 *
 * 示例 5：
 *      输入：s = "Alice does not even like bob"
 *      输出："bob like even not does Alice"
 *
 *
 */
public class ReverseWord_151 {

    public static String solution_01(String str){
        str = str.trim();
        List<String> list = Arrays.asList(str.split("\\s+"));
        Collections.reverse(list);
        return String.join(" ", list);
    }


    public static String solution_02(String str){
        //移除多余的空格
        StringBuilder sb = removeSpaces(str);
        //翻转整个字符串
        reverse(sb, 0, sb.length()-1);
        //翻转单个单词
        reverseWord(sb);
        return sb.toString();
    }

    public static void reverseWord(StringBuilder sb){
        int len = sb.length();
        int slow = 0, fast = 0;
        while (slow < len){
            while (fast < len && sb.charAt(fast) != ' '){
                fast++;
            }
            reverse(sb, slow, fast-1);
            slow = fast + 1;
            fast++;
        }
    }

    public static void reverse(StringBuilder sb, int left, int right){
        while (left < right){
            char tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);
        }
    }

    public static StringBuilder removeSpaces(String str){
        int left = 0, right = str.length()-1;

        while (left <= right && str.charAt(left) == ' '){
            ++left;
        }
        while (right >= left && str.charAt(right) == ' '){
            --right;
        }

        StringBuilder sb = new StringBuilder();
        while (left <= right){
            char c = str.charAt(left);
            if (c != ' '){
                sb.append(c);
            }else if(sb.charAt(sb.length()-1) != ' '){
                sb.append(c);
            }
            left++;
        }
        return sb;
    }

    public static void main(String[] args) {
        String str = " the sky   is blue  ";
        String tmp1 = solution_01(str);
        String tmp2 = solution_02(str);
        System.out.println(tmp1);
        System.out.println(tmp2);
    }


}
